package com.lht.arithmetic.sort;

/**
 * @author Eric
 * @version 1.0
 * @date 2019-11-25
 */
public class QuickSort implements Sort {

    @Override
    public void sort(int[] arr, int start, int end) {
        int middle = getIndex(arr, start, end);
        if (start < middle - 1) {
            // 这里不判断，执行的 getIndex high 会变成负数 然后死循环
            sort(arr, start, middle - 1);
        }
        if (end > middle + 1) {
            sort(arr, middle + 1, end);
        }
    }

    /**
     * 快速排序的核心思想： 获取一个值，然后 low 指针 和high指针，比较，如果 arr[low] >= tmp  and arr[high] < tmp
     * 则 arr[low] exchange arr[high]
     *
     * @param arr  1
     * @param l    2
     * @param high 3
     * @return int
     * @throws
     * @author Eric
     * @date 2019/11/25
     **/
    public int getIndex(int[] arr, int l, int high) {
        int low = l;
        int piovt = arr[low];
        while (low < high) {
            while (low < high && arr[high] > piovt) {
                high--;
            }
            while (low < high && arr[low] <= piovt) {
                low++;
            }
            if (low < high) {
                // 交换两者的数
                int tmp = arr[low];
                arr[low] = arr[high];
                arr[high] = tmp;
            }
        }

        // 所有low 都是比较上面，我拿 最大low 就是拿到一个 比 povit小的值
        int tmp = arr[l];
        arr[l] = arr[low];
        arr[low] = tmp;

        return low;
    }
}
